import java.util.*;

/**
 * 给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
 * 要求输出所有火车出站的方案，以字典序排序输出。
 */
public class HJ77 {
    public static void main(String[] args) {
        /*
        * 队列表示未进站的火车先进先出
        * 栈表示已进站的火车先进后出
        * 每次火车进站后有两种选择：1.直接出站 2.等待下列火车进站
         */
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int n = scanner.nextInt();
            //未进站的火车
            LinkedList<Integer> list = new LinkedList<>();
            //已进站的火车
            Stack<Integer> stack = new Stack<>();

            for (int i = 1; i <= n; i++) {
                list.add(i);
            }
            ArrayList<String> outList = new ArrayList<>();

            GetTrainList(list,stack,"",outList);

            Collections.sort(outList);

            for (String s : outList) {
                System.out.println(s);
            }
        }
    }

    private static void GetTrainList(LinkedList<Integer> list, Stack<Integer> stack, String s, ArrayList<String> outList) {
        if(list.isEmpty() && stack.isEmpty()){
            outList.add(s.trim());
            return;
        }
        //已入栈的出栈，更新outStr
        if(!stack.isEmpty()){
            LinkedList<Integer> tempList = new LinkedList<>(list);
            Stack<Integer> tempStack = (Stack<Integer>) stack.clone();
            String tempStr = s+tempStack.pop()+" ";
            GetTrainList(tempList,tempStack,tempStr,outList);
        }

        if(!list.isEmpty()){
            LinkedList<Integer> templist1 = new LinkedList<>(list);
            Stack<Integer> tempStack1 = (Stack<Integer>) stack.clone();
            tempStack1.push(templist1.poll());
            GetTrainList(templist1,tempStack1,s,outList);

        }
    }
}
